package com.zjsru.leetcode75.level1;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @Author: cookLee
 * @Date: 2023-11-05
 * Dota2 参议院
 */
public class PredictPartyVictory {


    /**
     * 主
     * \
     * 输入：senate = "RD"
     * 输出："Radiant"
     * 解释：
     * 第 1 轮时，第一个参议员来自 Radiant 阵营，他可以使用第一项权利让第二个参议员失去所有权利。
     * 这一轮中，第二个参议员将会被跳过，因为他的权利被禁止了。
     * 第 2 轮时，第一个参议员可以宣布胜利，因为他是唯一一个有投票权的人。
     * \
     * 输入：senate = "RDD"
     * 输出："Dire"
     * 解释：
     * 第 1 轮时，第一个来自 Radiant 阵营的参议员可以使用第一项权利禁止第二个参议员的权利。
     * 这一轮中，第二个来自 Dire 阵营的参议员会将被跳过，因为他的权利被禁止了。
     * 这一轮中，第三个来自 Dire 阵营的参议员可以使用他的第一项权利禁止第一个参议员的权利。
     * 因此在第二轮只剩下第三个参议员拥有投票的权利,于是他可以宣布胜利
     * \
     * @param args args
     */
    public static void main(String[] args) {
        PredictPartyVictory predictPartyVictory = new PredictPartyVictory();
        String senate = "RDRDRDRDR";
        System.out.println(predictPartyVictory.predictPartyVictory(senate));
    }

    public String predictPartyVictory(String senate) {
        Deque<Integer> stackR = new ArrayDeque<Integer>();
        Deque<Integer> stackD = new ArrayDeque<Integer>();
        for (int i = 0; i < senate.length(); i++) {
            if(senate.charAt(i) == 'R'){
                stackR.offer(i);
            }else{
                stackD.offer(i);
            }
        }
        while(!stackR.isEmpty() && !stackD.isEmpty()){
            Integer r = stackR.poll();
            Integer d = stackD.poll();
            //代表R有权利禁止D发言,同时将元素压到队列尾
            if(r < d){
                stackR.offer(r + senate.length());
            }else{
                stackD.offer(d + senate.length());
            }
        }
        return !stackR.isEmpty() ? "Radiant" : "Dire";
    }
}
